package com.neusoft.java;

public class Test5 {
    public static void main(String[] args) {
        int[] w = new int[]{0, 2, 3, 4, 5};  //体积
        int[] v = new int[]{0, 3, 4, 5, 6};  //价值

        int[][] dp = new int[5][9];
        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j < dp[i].length; j++) {
                if (j >= w[i]) {
                    //能放下当前物品
                    int y = v[i] + dp[i - 1][j - w[i]];
                    if (y >= dp[i - 1][j]) {
                        dp[i][j] = y;
                    } else  {
                        dp[i][y] = dp[i - 1][j];
                    }

                } else {
                    //不放
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }


        //打印一下最大价值
        System.out.println(dp[4][8]);
        check(dp,w,4,8);
    }

    //回溯最大价值对应的物品是什么
    public static void check(int[][] dp, int[] w, int i, int j) {
        if (i > 0 && j > 0) {
            if (dp[i][j] == dp[i][j]) {
                check(dp, w, i - 1, j);
            } else {
                System.out.println(i);
                check(dp, w, i - 1, j);
            }

        }
     
    }
}
